<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>动态规划解通配符匹配问题</title>
    </head>
    <body>
        <script>
            /**
             *  给定一个字符串 ( s ) 和一个字符模式 (p) ，实现一个支持 ' ? ' 和 ' * ' 的通配符匹配。
             * 
             *      '?' 可以匹配任何单个字符。
                    '*' 可以匹配任意字符串（包括空字符串）。

                两个字符串完全匹配才算匹配成功。

                说明:   
                        s 可能为空，且只包含从 a - z 的小写字母。 
                        p 可能为空，且只包含从 a - z 的小写字母，以及字符 ? 和 *。

                输入: s = "aa" p ="a" 
                输出: false 
                解释: " a " 无法匹配 " a a " 整个字符串。

                输入: s = "aa" p = "*" 
                输出: true 
                解释: '*' 可以匹配任意字符串。
                
                输入: s = "cb" p = "?a" 
                输出: false 
                解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

                输入: s = "adceb" p = "*a*b" 
                输出: true 
                解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

                输入: s = "acdcb" p = "a*c?b" 
                输出: false


                问题分析：
                    通配符匹配，如果p的某个位置是字母，那么他只能和s的字母匹配，如果p的某个位置 是“ ? ”字符，
                    那么他可以匹配s的任何字母，如果p的某个位置是“ * ”字符，那么他可以匹 配s的任意多个字母。

                1，状态定义 dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。我们最后只需要返回 
                    dp[s.length][p.length]即可 
                2，状态转移 这里分两种情况，一种是p的第j个字符不是*，一个是p的第j个字符是*。 
                    p的第j个字符不是* 
                        if ( s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1)== '?') 
                            dp[i][j] = dp[i - 1][j - 1]; 
                    p的第j个字符是* 
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];

                
             *
             * */
            // 两个字符串 s p
            function isMatch(s, p) {
                if (s.length === 0 || p.length === 0) {
                    return false;
                }
                var slen = s.length,
                    plen = p.length;
                var dp = [];
                for (let i = 0; i <= slen; i++) {
                    dp[i] = [];
                    for (let j = 0; j <= plen; j++) {
                        dp[i][j] = null;
                    }
                }
                dp[0][0] = true;
                // 边界化初始条件
                for (let j = 1; j <= plen && dp[0][j - 1]; j++) {
                    dp[0][j] = p.charAt(j - 1) == "*";
                }

                for (let i = 1; i <= slen; i++) {
                    for (let j = 1; j <= plen; j++) {
                        var si = s.charAt(i - 1),
                            pj = p.charAt(j - 1);
                        // 下面是动态规划的状态转移方程
                        if (si == pj || pj == "?") {
                            dp[i][j] = dp[i - 1][j - 1];
                        } else if (pj == "*") {
                            dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                        }
                    }
                }
                return dp[slen][plen];
            }

            var s = "adceb";
            var p = "*a*b";
            console.log(isMatch(s, p));
        </script>
    </body>
</html>
